import sys
import os
import heapq

#节点类
class Vertex:
    def __init__(self, node):
        self.id = node#节点名称
        self.adjacent = {}#节点与其相邻节点的距离
        self.distance = sys.maxsize#节点与起点的距离       
        self.visited = False#节点是否被访问过  
        self.previous = None#起点到节点最短路径的上一个节点

    #添加邻居
    def add_neighbor(self, neighbor, weight=0):
        self.adjacent[neighbor] = weight

    #获取与节点相邻节点的信息
    def get_connections(self):
        return self.adjacent.keys()  

    #获取节点名称
    def get_id(self):
        return self.id

    #获取节点与某一节点的距离
    def get_weight(self, neighbor):
        return self.adjacent[neighbor]

    #设置节点与起点的距离 
    def set_distance(self, dist):
        self.distance = dist

    #获取节点与起点的距离 
    def get_distance(self):
        return self.distance

    #设置起点到节点最短路径的上一个节点
    def set_previous(self, prev):
        self.previous = prev

    #设置节点是否被访问过
    def set_visited(self):
        self.visited = True

    #放回这个类的描述信息
    def __str__(self):
        return str(self.id) + ' adjacent: ' + str([x.id for x in self.adjacent])
    
    #重载<符号
    def __lt__(self,n):
        return (self.distance<n.distance)

#图类
class Graph:
    def __init__(self):
        self.vert_dict = {}
        self.num_vertices = 0

    #迭代器
    def __iter__(self):
        return iter(self.vert_dict.values())

    #添加节点
    def add_vertex(self, node):
        self.num_vertices = self.num_vertices + 1
        new_vertex = Vertex(node)
        self.vert_dict[node] = new_vertex
        return new_vertex

    #获取名称对应的节点
    def get_vertex(self, n):
        if n in self.vert_dict:
            return self.vert_dict[n]
        else:
            return None

    #添加边
    def add_edge(self, frm, to, cost = 0):
        if frm not in self.vert_dict:
            self.add_vertex(frm)
        if to not in self.vert_dict:
            self.add_vertex(to)
        self.vert_dict[frm].add_neighbor(self.vert_dict[to], cost)
        self.vert_dict[to].add_neighbor(self.vert_dict[frm], cost)

    #获取图中所有节点
    def get_vertices(self):
        return self.vert_dict.keys()

#获取从起点到v的最短路径
def shortest(v, path):
    ''' make shortest path from v.previous'''
    if v.previous:
        path.append(v.previous.get_id())
        shortest(v.previous, path)
    return

#迪杰斯特拉算法
def dijkstra(aGraph, start, target):
    print('''Dijkstra's shortest path''')
    start.set_distance(0)
    unvisited_queue = [(v.get_distance(),v) for v in aGraph]
    heapq.heapify(unvisited_queue)

    while len(unvisited_queue):
        uv = heapq.heappop(unvisited_queue)
        current = uv[1]
        current.set_visited()
        for next in current.adjacent:
            if next.visited:
                continue
            new_dist = current.get_distance() + current.get_weight(next)
            
            if new_dist < next.get_distance():
                next.set_distance(new_dist)
                next.set_previous(current)
                print('updated : current = %s next = %s new_dist = %s' \
                        %(current.get_id(), next.get_id(), next.get_distance()))
            else:
                print('not updated : current = %s next = %s new_dist = %s' \
                        %(current.get_id(), next.get_id(), next.get_distance()))

        while len(unvisited_queue):
            heapq.heappop(unvisited_queue)
        unvisited_queue = [(v.get_distance(),v) for v in aGraph if not v.visited]
        heapq.heapify(unvisited_queue)
    

g = Graph()#创建一个图

count=0#记录边数
with open ('ospf.txt','r') as f:
    for line in f:
	    count+=1

satir=count-1

#读取文件中信息初始化图
f.close()	
myf=open('ospf.txt','r')
x=myf.readline()
while(satir!=0):
     a=x[0]
     b=x[1]
     c=int(x[2])
     x=myf.readline()
     g.add_edge(a,b,c)  
     satir=satir-1
myf.close()
print('Graph data:')
for v in g:
    for w in v.get_connections():
        vid = v.get_id()
        wid = w.get_id()
        print('( %s , %s, %3d)'  % ( vid, wid, v.get_weight(w)))
#求节点a到d的最短路径
dijkstra(g, g.get_vertex('a'), g.get_vertex('d')) 
#输出节点a到d的最短路径
target = g.get_vertex('d')
path = [target.get_id()]
shortest(target, path)
print('The shortest path : %s' %(path[::-1]))